package 动态规划;
//https://www.nowcoder.com/practice/166eaff8439d4cd898e3ba933fbc6358?tpId=46&tqId=29117&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking
public class 不同路径的数目一 {
    public int uniquePaths (int m, int n) {
        return fun_1(m , n);
    }
    public int fun_1(int m , int n ){
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1 ; i <= m ; i ++ ){
            for (int j = 1 ; j <= n ; j ++){
                if (i == 1){
                    dp[i][j] = 1;
                    continue;
                }
                if (j == 1){
                    dp[i][j] = 1;
                    continue;
                }
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m][n];
    }
    public int fun_2(int m , int n){
        if (m == 1 || n == 1){
            return 1;
        }
        return fun_2(m - 1 , n ) + fun_2(m ,n - 1);
    }
}

